package cn.dglydrpy.study.algorithm.learning.recursive2DP;

/**
 * 暴力递归到动态规划的套路
 * 
 * 什么暴力递归可以继续优化？
 * 有重复调用同一个子问题的解，这种递归可以优化
 * 如果每一个子问题都是不同的解，无法优化也不用优化
 * 
 * 暴力递归和动态规划的关系
 * 某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
 * 任何动态规划问题，都一定对应着某一个有重复过程的暴力递归
 * 但不是所有的暴力递归，都一定对应着动态规划
 * 
 * 面试题和动态规划的关系
 * 解决一个问题，可能有很多尝试方法
 * 可能在很多尝试方法中，又有若干个尝试方法有动态规划的方式
 * 一个问题   可能有   若干种动态规划的解法
 * 
 * 如何找到某个问题的动态规划方式？
 * 1）设计暴力递归：重要原则+4种常见尝试模型！重点！
 * 2）分析有没有重复解：套路解决
 * 3）用记忆化搜索 -> 用严格表结构实现动态规划：套路解决
 * 4）看看能否继续优化：套路解决
 * 
 * 面试中设计暴力递归过程的原则
 * 1）每一个可变参数的类型，一定不要比int类型更加复杂
 * 2）原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参数
 * 3）如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可
 * 4）可变参数的个数，能少则少
 * 
 * 知道了面试中设计暴力递归过程的原则，然后呢？
 * 一定要逼自己找到不违反原则情况下的暴力尝试！
 * 如果你找到的暴力尝试，不符合原则，马上舍弃！找新的！
 * 如果某个题目突破了设计原则，一定极难极难，面试中出现概率低于5%
 * 
 * 常见的4种尝试模型:
 * 1）从左往右的尝试模型
 * 2）范围上的尝试模型
 * 3）多样本位置全对应的尝试模型
 * 4）寻找业务限制的尝试模型
 * 
 * 如何分析有没有重复解
 * 列出调用过程，可以只列出前几层
 * 有没有重复解，一看便知
 * 
 * 暴力递归到动态规划的套路
 * 1）你已经有了一个不违反原则的暴力递归，而且的确存在解的重复调用
 * 2）找到哪些参数的变化会影响返回值，对每一个列出变化范围
 * 3）参数间的所有的组合数量，意味着表大小
 * 4）记忆化搜索的方法就是傻缓存，非常容易得到
 * 5）规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解
 * 6）对于有枚举行为的决策过程，进一步优化
 * 
 * 动态规划的进一步优化
 * 1）空间压缩
 * 2）状态化简
 * 3）四边形不等式
 * 4）其他优化技巧
 * 
 * 
 */

/**
 * 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
 * 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
 * 如果机器人来到1位置，那么下一步只能往右来到2位置；
 * 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
 * 如果机器人来到中间位置，那么下一步可以往左走或者往右走；
 * 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
 * 给定四个参数 N、M、K、P，返回方法数。 
 */
public class Code06_RobotWalk {

	/**
	 * 暴力尝试
	 * @param N
	 * @param start
	 * @param aim
	 * @param K
	 * @return
	 */
	public static int ways1(int N, int start, int aim, int K) {
		if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
			return -1;
		}
		return process1(start, K, aim, N);
	}

	// 机器人当前来到的位置是cur，
	// 机器人还有rest步需要去走，
	// 最终的目标是aim，
	// 有哪些位置？1~N
	// 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
	public static int process1(int cur, int rest, int aim, int N) {
		if (rest == 0) { // 如果已经不需要走了，走完了！
			return cur == aim ? 1 : 0;
		}
		// (cur, rest)
		if (cur == 1) { // 1 -> 2
			return process1(2, rest - 1, aim, N);
		}
		// (cur, rest)
		if (cur == N) { // N-1 <- N
			return process1(N - 1, rest - 1, aim, N);
		}
		// (cur, rest)
		return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
	}

	/**
	 * 傻缓存法
	 * @param N
	 * @param start
	 * @param aim
	 * @param K
	 * @return
	 */
	public static int ways2(int N, int start, int aim, int K) {
		if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
			return -1;
		}
		int[][] dp = new int[N + 1][K + 1];
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= K; j++) {
				dp[i][j] = -1;
			}
		}
		// dp就是缓存表
		// dp[cur][rest] == -1 -> process1(cur, rest)之前没算过！
		// dp[cur][rest] != -1 -> process1(cur, rest)之前算过！返回值，dp[cur][rest]
		// N+1 * K+1
		return process2(start, K, aim, N, dp);
	}

	// cur 范围: 1 ~ N
	// rest 范围：0 ~ K
	public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
		if (dp[cur][rest] != -1) {
			return dp[cur][rest];
		}
		// 之前没算过！
		int ans = 0;
		if (rest == 0) {
			ans = cur == aim ? 1 : 0;
		} else if (cur == 1) {
			ans = process2(2, rest - 1, aim, N, dp);
		} else if (cur == N) {
			ans = process2(N - 1, rest - 1, aim, N, dp);
		} else {
			ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
		}
		dp[cur][rest] = ans;
		return ans;

	}

	/**
	 * 动态规划
	 * @param N
	 * @param start
	 * @param aim
	 * @param K
	 * @return
	 */
	public static int ways3(int N, int start, int aim, int K) {
		if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
			return -1;
		}
		int[][] dp = new int[N + 1][K + 1];
		dp[aim][0] = 1;
		for (int rest = 1; rest <= K; rest++) {
			dp[1][rest] = dp[2][rest - 1];
			for (int cur = 2; cur < N; cur++) {
				dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
			}
			dp[N][rest] = dp[N - 1][rest - 1];
		}
		return dp[start][K];
	}

	public static void main(String[] args) {
		System.out.println(ways1(5, 2, 4, 6));
		System.out.println(ways2(5, 2, 4, 6));
		System.out.println(ways3(5, 2, 4, 6));
	}

}
